package leecode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class LeetCode15 {
    //第一题
    //给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
    List<List<Integer>>list=new ArrayList<>();
    Deque<Integer>path=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root,target);
        return list;
    }
    public void dfs(TreeNode root,int k){
        if(root==null){
            return;
        }
        path.addFirst(root.val);
        k-=root.val;
        if(root.right==null&&root.left==null&&k==0){
            list.add((List<Integer>) path);
        }
        dfs(root.right,k);
        dfs(root.left,k);
        path.pollLast();
    }

    /**
     * 把树转化为双向链表
     */
    TreeNode pre,head;
    public TreeNode treeToDoublyList(TreeNode root) {
        if(root==null){
            return null;
        }
        dfs1(root);
        head.left=pre;
        pre.right=head;
        return head;
    }
    private void dfs1(TreeNode cur) {
        if (cur==null){
            return;
        }
        dfs1(cur.left);
        if(pre!=null){
            pre.right=cur;
        }else {
            head=cur;
        }
        cur.left=pre;
        pre=cur;
        dfs1(cur.right);
    }

    //第三题返回第k个节点
    List<Integer>list2=new ArrayList<>();
    public void display(TreeNode treeNode){
        if(treeNode==null){
            return;
        }
        display(treeNode.left);
        list2.add(treeNode.val);
        display(treeNode.right);
    }
    public int kthLargest(TreeNode root, int k) {
        display(root);
        return (list2.get(list2.size()-k));
    }

    public static void main(String[] args) {
        TreeNode treeNode1=new TreeNode(1);
        TreeNode treeNode2=new TreeNode(2);
        TreeNode treeNode3=new TreeNode(3);
        TreeNode treeNode4=new TreeNode(4);
        treeNode3.left=treeNode1;
        treeNode1.right=treeNode2;
        treeNode3.right=treeNode4;
        LeetCode15 leetCode15=new LeetCode15();
        leetCode15.kthLargest(treeNode3,1);

    }
}
